68. 文本左右对齐

Similar Question

leading to the advanced question

Solution Tips

方案一: 贪心 + 模拟

/**
 * @param {string[]} words
 * @param {number} maxWidth
 * @return {string[]}
 */
var fullJustify = function(words, maxWidth) {

    // 每个单词需要跟一个空格, 除非是最后一个
    const res = [];
    let line = [];
    let wordAccWidth = 0;
    let lineWordCount = 0;
    for (let i = 0; i < words.length; i++) {
        const curWidth = wordAccWidth + words[i].length

        if (curWidth < maxWidth) {
            // + 1  是填充的空格位置
            // 即使填充了空格, 最多也是 === maxWidth, 无论如何也放不下一个新单词了
            line.push(words[i]);
            line.push(" ");
            wordAccWidth += words[i].length + 1;
            lineWordCount++;
        }
        else if (curWidth === maxWidth) {
            // 刚好等于的情况就是不用填充空格
            line.push(words[i]);
            wordAccWidth += words[i].length;
            res.push(line.join(''));
            line = [];
            wordAccWidth = 0;
            lineWordCount = 0;
        }
        else {
            // 如果是大于, 说明这一行不能放入新的单词了
            if (lineWordCount === 1) {
                // 如果只有一个单词, 依然是右侧填充空格, 所以此时不需要去除空格
                const total = maxWidth - wordAccWidth;
               //  所有的剩余位置都填充到末尾就行了
                line[line.length - 1] += ' '.repeat(total);
            }
            else {
                // 如果单词数大于2个, 需要去除最后一个空格, 然后根据剩余的字符数量填充空格
                if (lineWordCount >=2 && line[line.length - 1].includes(' ')) {
                    line.pop();
                    wordAccWidth -= 1;
                }
                const total = maxWidth - wordAccWidth;
                // 在除了第一个单词外的左侧进行填充, 每个左侧都需要填充 each 个
                const each = Math.floor(total / (lineWordCount - 1));
                // 剩余的在一次单词遍历中进行填充即可
                let rest = total % (lineWordCount - 1);
                // 遍历 line, 空格都在奇数位置
                for (let j = 1; j < line.length; j += 2) {
                    const padTime = rest > 0 ? each + 1 : each;
                    rest--;
                    line[j] = line[j] + ' '.repeat(padTime);
                }
            }

            res.push(line.join(''));
            line = [];
            wordAccWidth = 0;
            lineWordCount = 0;

            //  当前的 words[i] 还没有处理
            i--;
        }

        //  针对最后一行做特殊处理, 如果是刚好=== maxWidth, 就啥都不用处理
        if (i === words.length - 1 && lineWordCount !== 0) {
            line.push(' '.repeat(maxWidth - wordAccWidth));
            res.push(line.join(''));
        }
    }

    return res;
};


console.log(fullJustify(["ask","not","what","your","country","can","do","for","you","ask","what","you","can","do","for","your","country"], 16))
console.log(fullJustify(["This", "is", "an", "example", "of", "text", "justification."], 16))
console.log(fullJustify(["What","must","be","acknowledgment","shall","be"], 16))